package com.zhz.leetcode;

import com.zhz.leetcode.entity.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * 144. 二叉树的前序遍历
 * 给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
 * <p>
 * 示例 1：
 * 输入：root = [1,null,2,3]
 * 输出：[1,2,3]
 * <p>
 * 示例 2：
 * 输入：root = []
 * 输出：[]
 * <p>
 * 示例 3：
 * 输入：root = [1]
 * 输出：[1]
 * <p>
 * 示例 4：
 * 输入：root = [1,2]
 * 输出：[1,2]
 * <p>
 * 示例 5：
 * 输入：root = [1,null,2]
 * 输出：[1,2]
 * <p>
 * 提示：
 * 树中节点数目在范围 [0, 100] 内
 * -100 <= Node.val <= 100
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class BinaryTreePreorderTraversal144 {

    public static void main(String[] args) {
        BinaryTreePreorderTraversal144 m = new BinaryTreePreorderTraversal144();
        TreeNode root = new TreeNode(1, null, new TreeNode(2, new TreeNode(3), null));
//        TreeNode root = new TreeNode(1);
//        TreeNode root = new TreeNode(1,new TreeNode(2),null);
//        TreeNode root = new TreeNode(1, null, new TreeNode(2));
        List<Integer> list = m.preorderTraversal1(root);
        System.out.println(Arrays.toString(list.toArray()));
    }

    /**
     * 前序遍历
     * <p>
     * 先使用递归来实现
     */
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        list.add(root.val);
        list.addAll(preorderTraversal(root.left));
        list.addAll(preorderTraversal(root.right));
        return list;
    }


    /**
     * 进阶： 使用迭代来完成
     * 因为我们需要使用前序遍历，也就是 根->左->右
     * 使用栈来保存节点信息，一旦有做节点则往栈里面add进去，一旦发现没有左边节点了，则pop出一个，使其回到上一层的根节点，
     * 然后再从根节点的右节点开始往下遍历左节点，
     * 以此为基础进行迭代
     */
    public List<Integer> preorderTraversal1(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        while (!stack.isEmpty() || curr != null) {
            //一旦左边的根节点不为空，则往下遍历，并再每次循环的时候，curr = curr.left，让他往下一层遍历左节点
            while (curr != null) {
                list.add(curr.val);
                stack.push(curr);
                curr = curr.left;
            }
            //一旦左节点都遍历完成后，则将curr设置为右节点，并重新开始while迭代，继续开始遍历curr的左节点
            //此时stack.pop() 就时之前存入的curr的根节点
            curr = stack.pop().right;
        }
        return list;
    }


}
